package com.lqian.simplestructure.sorted;

import java.util.Arrays;

/**
 * 冒泡排序
 * 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
 * 一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作
 *
 * 冒泡过程可优化，当某次冒泡操作已经没有数据交换时，说明已经到达完全有序，不需要再执行后续的冒泡操作。
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {5,2,1,5,7,9,8,0};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr,arr.length);
        System.out.println(Arrays.toString(arr));

    }

    //冒泡排序 arr表示数组，n表示数组大小
    public static void bubbleSort(int[] arr,int n){
        if (n<=1) return;

        // 前后循环比较 共需要 n-1轮 （最后/最前面一个元素不需要比较）
        for (int i = 0; i <arr.length-1 ; i++) {
            //已经比较好的元素不需要再次比较
            //提前退出冒泡循环的标识位
            boolean flag = false;
            for (int j = 0; j <arr.length-1-i; j++) {
                //如果前一个元素比后一个元素大，就交换位置
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true; // 表示有数据交换
                }
            }
            if (!flag) break; //没有数据交换，提前退出
        }

    }
}
